package interviewClassic150;

import org.junit.Test;

public class ProductExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        //维护每个元素的前缀积（除了本身），后缀积（除了本身）
        int n = nums.length;
        int[] pre = new int[n];
        int[] post = new int[n];

        //初始化
        pre[0] = 1;
        post[n - 1] = 1;

        //维护
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
            post[n - 1 - i] = post[n - i] * nums[n - i];
        }

        //结果集
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = pre[i] * post[i];
        }

        return res;
    }

    @Test
    public void test() {
        int[] nums = {1,2,3,4};
        int[] ints = productExceptSelf(nums);
        System.out.println(ints);
    }
}
